type Item<T> = T & {
  children?: Item<T>[];
};

type key = number | string;

export function listToTree<T>(list: T[], getKey: (item: T) => key, getParentKey: (item: T) => key | null): Item<T>[] {
  const nodeMap = new Map<key, Item<T>>();
  const result: Item<T>[] = [];
  for (const node of list) {
    const key = getKey(node);
    nodeMap.set(key, { ...node, children: [] });
  }
  for (const node of list) {
    const parentKey = getParentKey(node);
    const key = getKey(node);
    const _node = nodeMap.get(key);
    if (!parentKey && _node) {
      result.push(_node);
    } else if (_node && parentKey) {
      const parentNode = nodeMap.get(parentKey);
      if (parentNode) {
        parentNode.children?.push(_node);
      }
    }
  }
  return result;
}
